package com.hanlin.leetcode;

import com.hanlin.day03.Alternator;

/**
 * 给定长度为2n的整数数组 nums ，你的任务是将这些数分成n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，
 * 使得从 1 到n 的 min(ai, bi) 总和最大。
 * <p>
 * 返回该 最大总和 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,4,3,2]
 * 输出：4
 * 解释：所有可能的分法（忽略元素顺序）为：
 * 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
 * 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
 * 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
 * 所以最大总和为 4
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [6,2,6,5,1,2]
 * 输出：9
 * 解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/array-partition-i
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: hl.yuan
 * @Date: 2021/6/3 16:34
 */
public class ArraySplitting {

    /**
     * 这里的解题思路就是需要把数组给排序一下，然后在进行计算。这里就排序可以用：选择排序、插入排序、冒泡排序
     *
     * @param nums
     * @return
     */
    public static int arrayPairSum(int[] nums) {
        /* 这里先使用冒泡排序
        for (int i = nums.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    exchange(nums, j, j + 1);
                }
            }
        }
        */
        /*
         * 选择排序：每次循环挑出最小的，
         *
            for (int i = 0; i <= nums.length - 1; i++) {
                // 假设第一个位置最小
                int minValueIndex = i;
                for (int j = i; j <= nums.length - 1; j++) {
                    if (nums[minValueIndex] > nums[j]){
                        minValueIndex = j;
                    }
                }
                exchange(nums,minValueIndex,i);
            }
        * */
        // 插入排序 ：每次循环从 左侧开始比。

        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    exchange(nums, j, j - 1);
                } else {
                    break;
                }
            }
        }
        Alternator.printArray(nums);

        int sum = 0;
        int arrayIndex = 0;
        while (arrayIndex < nums.length) {
            int min = Math.min(nums[arrayIndex], nums[arrayIndex + 1]);
            sum += min;
            arrayIndex = arrayIndex + 2;
        }
        return sum;
    }

    /**
     * 交换值
     *
     * @param array
     * @param a
     * @param b
     */
    public static void exchange(int[] array, int a, int b) {
        int item = array[a];
        array[a] = array[b];
        array[b] = item;

    }

    public static void main(String[] args) {
        int param[] = {1, 4, 3, 2};

        int sum = arrayPairSum(param);

        System.out.println(sum);
    }

}
